package com.LeeCode;

import java.util.Arrays;

/**
 * 所有排列中的最大和
 */

public class Code1589 {
    public static void main(String[] args) {

    }

    public int maxSumRangeQuery(int[] nums, int[][] requests) {
        int MOD = 1000000007;
        int n = nums.length;
        int[] diff = new int[n + 1];

        for (int[] request : requests) {
            diff[request[0]]++;
            diff[request[1] + 1]--;
        }

        int sum = 0;
        int[] freq = new int[n];
        for (int i = 0; i < n; i++) {
            sum += diff[i];
            freq[i] = sum;
        }

        long ans = 0;
        Arrays.sort(freq);
        Arrays.sort(nums);
        for(int i = n-1; i >= 0; i--) {
            if(freq[i] == 0) break;
            ans += (long) freq[i] * nums[i];
        }

        return (int) (ans % MOD);
    }
}
